import java.util.Stack;

class Solution {
    public static String decodeString(String s) {
        // 创建一个数字栈、一个字符串栈
        Stack<String> s_stack = new Stack<>();
        Stack<Integer> n_stack = new Stack<>();
        s_stack.push(""); // 避免纯字符前缀无法添加到栈顶元素的末尾
        int n = s.length(), i = 0;
        char[] strs = s.toCharArray();
        while (i < n) {
            if (strs[i] >= '0' && strs[i] <= '9') { // 数字
                int num = 0;
                while (strs[i] >= '0' && strs[i] <= '9') { // 可能不止一位数
                    num = num * 10 + (strs[i] - '0');
                    i++;
                }
                n_stack.push(num); // 数字入栈
            } else if (strs[i] == '[') { // 左括号
                // 字符串入栈
                i++;
                StringBuilder builder = new StringBuilder();
                while (strs[i] != ']' && strs[i] <= '0' && strs[i] >= '9') {
                    builder.append(strs[i++]);
                }
                s_stack.push(builder.toString());
            } else if (strs[i] == ']') { // 右括号
                // 字符串栈 出栈，数字栈 出栈
                StringBuilder builder = new StringBuilder(s_stack.pop());
                StringBuilder tmp = new StringBuilder(builder);
                int k = n_stack.pop();
                for (int j = 0; j < k-1; j++) {
                    tmp.append(builder);
                }
                // 添加到栈顶元素的末尾
                builder = new StringBuilder(s_stack.pop());
                s_stack.push(builder.append(tmp).toString());
                i++;
            } else { // 纯字符串
                // 拿到字符串
                StringBuilder tmp = new StringBuilder();
                while (i < n && strs[i] >= 'a' && strs[i] <= 'z') {
                    tmp.append(strs[i++]);
                }
                // 直接添加到栈顶元素的末尾
                StringBuilder builder = new StringBuilder(s_stack.pop());
                builder.append(tmp);
                s_stack.push(builder.toString());
            }
        }
        return s_stack.pop().toString();
    }

    public static void main(String[] args) {
        System.out.println(decodeString("100[leetcode]"));
//        System.out.println(decodeString("3[a2[c]]"));
//        System.out.println(decodeString("3[a]2[bc]"));
    }
}